<head>
    <meta charset="UTF-8">
<title>算法训练 Abbott’s Revenge</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>在1999年的World Finals中有一个基于Dice Maze(骰子迷宫)的题目。在出题人编写那道题目的时候，他们并没有发现这种迷宫的创意来源。然而在那场比赛结束不久，创作了大量的这种迷宫的Robert Abbott先生，联系了比赛主办方并确认自己是骰子迷宫的原作者。我们很遗憾没有在去年的题目描述中感谢Abbott先生的原创意，但我们很高兴Abbott先生主动为今年的比赛提供他原创的、未公开的&ldquo;步行通过的箭头迷宫&rdquo;。</div>
<div>与大多数的迷宫相同，箭头迷宫也是每次从一个路口走到另一个路口，直到到达终点。在每个路口处，如果你从某个方向进入了该路口，那么路口的地面上在靠近你的方向会画有一组箭头，它们相对于你的方向可以是向左，向前，向右，或者是它们的任意组合。</div>
<div>图1描述了一个箭头迷宫。每个路口用二维坐标(x,y)表示，以左上角的路口为(1,1)。在图1给出的迷宫中，起点的坐标是(3,1)，终点的坐标是(3,3)。在你开始后，你只能向北走1步到达(2,1)。由于你是从南边到达(2,1)这一点的，而这一点在南边的箭头是向前指的，所以你只能继续向前走到达(1,1)。在此之后，由于你是从南边到达了(1,1)，这一点在南边的箭头是向右指的，所以你也只能向右拐，到达(1,2)。到目前为止，你还没有做出任何选择。以此类推，你会接着依次经过(2,2) (2,3) (1,3) (1,2)。现在你可以选择继续向前走或者向左转。如果你向前走，你会回到(1,1)，而向左转可以让你到达(2,2)。事实上，唯一最优的方案是依次经过以下路口：(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3)。</div>
<div>你需要写一个程序解决这个迷宫。&ldquo;解决&rdquo;的意义是：只要迷宫是可解的，你就要找到一条路线，它必须在起点沿指定的方向走出，并最终到达终点，当然，路线的长度需要是所有方案中最短的。<br />
<img src="http://lx.lanqiao.cn/RequireFile.do?fid=Lt9MMyqm" width="442" height="428" alt="" /></div>
<p>【输入格式】</p>
<div>输入文件包括一个或多个箭头迷宫。每个迷宫描述的第一行是这个迷宫的名称，保证它只由数字和字母组成且长度不超过20。接下来的一行依次包含了起点的坐标，起始时方向，目标点的坐标，以空格隔开。本题的迷宫最大尺寸为9&times;9，所以行与列的编号均为1到9。起始时的方向为N,S,E,W之一，分别代表北、南、西、东。</div>
<div>剩下的若干行按照以下格式输入：一对整数，若干字符串，以星号(*)结束，以空格隔开。每一行代表一个路口，一对整数表示路口的坐标。对于每一个字符串，第一位为N,S,E,W之一，接下来若干位只可能包含L,F,R，分别代表向左，向前，向右。这个字符串的含义是：朝向某个方向进入该路口(所以箭头被画在这个路口的相反方向)，接下来就只能向某个方向继续行走。</div>
<div>对于每个迷宫，以0作为一行的结束，从接下来一行开始就是一个新的箭头迷宫。输入文件以单独的一行END作为结尾。</div>
<p>【输出格式】</p>
<div>对于每个箭头迷宫，应该先输出它的名字，然后接下来若干行，输出一个路径，格式如问题描述中所述；或者输出&quot;No Solution Possible&quot;。迷宫的名字应从第1列开始，而其余所有的行都从第3列开始，即行首有2个空格。对于输出的每个路径，除最后一行外，每行须输出恰好10个路口(坐标)。</div>
<div>在下面的样例中，输入的第一个迷宫是图1中的迷宫。<br />
注意，在下面的样例输出当中，除了SAMPLE和NOSOLUTION两行以外，其余的行首都需要空两格！（由于格式化问题未能显示出来）</div>
<p>【样例输入】</p>
<div>SAMPLE</div>
<div>3 1 N 3 3</div>
<div>1 1 WL NR *</div>
<div>1 2 WLF NR ER *</div>
<div>1 3 NL ER *</div>
<div>2 1 SL WR NF *</div>
<div>2 2 SL WF ELF *</div>
<div>2 3 SFR EL *</div>
<div>0</div>
<div>NOSOLUTION</div>
<div>3 1 N 3 2</div>
<div>1 1 WL NR *</div>
<div>1 2 NL ER *</div>
<div>2 1 SL WR NFR *</div>
<div>2 2 SR EL *</div>
<div>0</div>
<div>END</div>
<p>【样例输出】</p>
<div>SAMPLE</div>
<div>&nbsp; (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)</div>
<div>&nbsp; (2,2) (1,2) (1,3) (2,3) (3,3)</div>
<div>NOSOLUTION</div>
<div>&nbsp; No Solution Possible</div>
<p>【数据规模和约定】<br />
设T为数据组数：对于30%的数据，T=1；对于60%的数据，T&le;100；对于100%的数据，T&le;1000。</p>